#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;
// 动态编程
//
// array
// {75, 105, 120, 75, 90, 135}
// result
// result 上的每一个位置，就表示 array 对应位置上能计算出来的最大不相邻和
// result[0] array[0] 能计算出来的最大不相邻和
// result[1] array[0-1] 能计算出来的最大不相邻和
// result[2] array[0-2] 能计算出来的最大不相邻和
// ...
// i = 2
// result
// {75, 105，195, 195, 285, 195 + 135}
// *(result.end() - 1)
// *(result.rbegin())
// 一个数字的时候，最大不相邻和就是它自己
// 两个数字的时候，最大不相邻和是两个中较大的一个
// result[i] 有两种可能
// 第一种情况：array[i] + result[i - 2] = 120 + 75 = 195
// 第二种情况：result[i - 1] = 105

int maxSum(vector<int> array) {
  // 初始情况
  if (array.size() == 0) {
    return 0;
  }
  else if (array.size() == 1) {
    return array[0];
  }

  vector<int> result = array;
  // result[0] = array[0]
  result[1] = max(array[0], array[1]);

  for (int i = 2; i < array.size(); ++i) {
    int sum1 = array[i] + result[i - 2];
    int sum2 = result[i - 1];
    result[i] = max(sum1, sum2);
  }

  return *result.rbegin();
}
// {75, 105, 120, 75, 90, 135}

int main(int argc, char const *argv[])
{
  /* code */
  return 0;
}
